package com.tianyuan.test2;
import java.util.*;
//TODO
/**
 * 有重复项数字的全排列
 *
 * @date 2025/10/21 15:28
 * 给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
 * 数据范围：0<n≤8，数组中的值满足-1≤val≤5
 *
 * 输入：[1,1,2]   返回值：[[1,1,2],[1,2,1],[2,1,1]]
 * 输入：[0,1]   返回值：[[0,1],[1,0]]
 */


public class Solution {
    // 存储最终所有不重复的全排列结果
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    // 存储当前正在构建的排列（临时排列）
    ArrayList<Integer> arry = new ArrayList<>();
    // 存储已选中元素的索引（利用索引唯一性标记已用元素）
    ArrayList<Integer> index = new ArrayList<>();
    /**
     * 入口方法：求解含重复元素的数组的全排列（结果按字典序升序）
     * @param num 输入的可能包含重复元素的数组
     * @return 所有不重复的全排列列表
     */
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // 每次调用前清空全局集合，避免多次测试结果干扰
        res.clear();
        arry.clear();
        index.clear();
        // 先对数组排序：确保结果按字典序升序排列，同时辅助去重
        Arrays.sort(num);
        // 调用递归方法开始构建排列
        permute(num);
        return res;
    }
    /**
     * 递归+回溯的核心方法：构建排列并去重
     * @param num 输入的数组
     */
    void permute(int[] num) {
        // 递归终止条件：已选索引数量等于数组长度，说明构建出一个完整排列
        if (index.size() == num.length) {
            res.add(new ArrayList<>(arry)); // 存入当前排列的副本
            return;
        }
        // 临时集合：记录当前递归层已选过的元素值（用于去重，避免同一层选相同值）
        ArrayList<Integer> temp = new ArrayList<>();
        for (int i = 0; i < num.length; i++) {
            // 去重逻辑：
            // 1. 索引i已被使用（存在于index中）→ 跳过
            // 2. 当前元素值已在本层被选过（存在于temp中）→ 跳过
            if (index.contains(i) || temp.contains(num[i])) {
                continue;
            }
            temp.add(num[i]); // 记录本层已选值
            index.add(i);     // 记录已用索引
            arry.add(num[i]); // 加入当前排列
            permute(num); // 递归构建下一个位置
            // 回溯：撤销当前选择
            index.remove(index.size() - 1);
            arry.remove(arry.size() - 1);
        }
    }








    public static void main(String[] args) {
        Solution solution = new Solution();
        // 测试用例1：输入[1,1,2]
        int[] test1 = {1, 1, 2};
        ArrayList<ArrayList<Integer>> result1 = solution.permuteUnique(test1);
        System.out.println("测试用例1输出：" + result1); // 预期：[[1,1,2],[1,2,1],[2,1,1]]
        // 测试用例2：输入[0,1]
        int[] test2 = {0, 1};
        ArrayList<ArrayList<Integer>> result2 = solution.permuteUnique(test2);
        System.out.println("测试用例2输出：" + result2); // 预期：[[0,1],[1,0]]
    }
}